#include "BinaryTree.h"

//Print data through preorder traversal - From Schwartz
void BinaryTree::prstringPreorder2(BinaryNode* node) 
{
    if (node != NULL) 
	{
        cout << node->getData();
        prstringPreorder2(node->getLeft());
		prstringPreorder2(node->getRight());
    }
}

//Print data through postorder traversal - From Schwartz
void BinaryTree::prstringPostorder2(BinaryNode* node) 
{
    if (node != NULL) 
	{
		prstringPostorder2(node->getLeft());
		prstringPostorder2(node->getRight());
        cout << node->getData();
    }
}

//Print data through in-order traversal - From Schwartz
void BinaryTree::prstringInorder2(BinaryNode* node) 
{
    if (node != NULL) 
	{
        prstringInorder2(node->getLeft());
        cout << node->getData();
        prstringInorder2(node->getRight());
    }
}

//Default constructor - From Schwartz
BinaryTree::BinaryTree() { root=NULL; }

//Constructor taking string as the root node - From Schwartz
BinaryTree::BinaryTree(string item) 
{
	root = new BinaryNode(item);
}

//Copy Constructor
BinaryTree::BinaryTree(const BinaryTree& other)
{
	BinaryNode* currNode = new BinaryNode(*(other.getRoot()));
	root = currNode;
}

//Copy Assignment Operator
BinaryTree& BinaryTree::operator=(const BinaryTree& other)
{
	if(this != &other)
	{
		delete root;
		root = new BinaryNode(*(other.getRoot()));
	}
	return *this;
}

//takes 2 binary trees and merges them
BinaryTree::BinaryTree(BinaryTree* bt1Ptr, BinaryTree* bt2Ptr)
{
	BinaryTree* tmpTree1 = new BinaryTree(*bt1Ptr);		//Store a temporary tree for tree1, so that we don't get rid of passed in tree
	BinaryTree* tmpTree2 = new BinaryTree(*bt2Ptr);		//Same for tree 2

	root = new BinaryNode(*(tmpTree1->getRoot()));		//New tree's root is tree 1's root

	while(tmpTree1->root != tmpTree1->getLowest())		//Until the last node is the root node
	{
		insert(new BinaryNode(*(tmpTree1->getLowest()))); //We insert the lowest node
		tmpTree1->removeNode(tmpTree1->getLowest()->data); //And then remove the lowest node
	}
	while(tmpTree2->root != tmpTree2->getLowest()) //Same here
	{
		insert(new BinaryNode(*(tmpTree2->getLowest())));
		tmpTree2->removeNode(tmpTree2->getLowest()->data);
	}
	insert(tmpTree2->getRoot()->data);		//Insert the second root node just to be sure
	
	delete tmpTree1;				//Get rid of both temporary trees
	delete tmpTree2;
}

//Gets the root node of the tree - From Schwartz
BinaryNode* BinaryTree::getRoot() const { return root; }

//Sets the root node of the tree - From Schwartz
void BinaryTree::setRoot(BinaryNode* r) { root = r; }

//Prints the Binary Tree - From Schwartz
string BinaryTree::ToTree() 
{
	char angle = (char)197;
	char horz = (char)196;
	char bar = (char)179;
	char c1[] = {angle,horz,horz,'\0'};
	char c2[] = {bar,' ',' ','\0'};
	string s1(c1);	
	string s2(c2);
    return root->ToTree(s2,s1);
}

//Call printing in preorder on the root of the binary tree - From Schwartz
void BinaryTree::prstringPreorder() 
{
    prstringPreorder2(root);
    cout << endl;
}

//Call printing in postorder on the root of the binary tree - From Schwartz
void BinaryTree::prstringPostorder() 
{
    prstringPostorder2(root);
    cout << endl;
}

//Call printing inorder on the root of the binary tree - From Schwartz
void BinaryTree::prstringInorder() 
{
    prstringInorder2(root);
    cout << endl;
}

//Returns true if a certain target string is somewhere in the tree - From Schwartz
bool BinaryTree::naivefind(string target) 
{
    return root->naivefind(target, root);
}

//Alternate insert with just a string
void BinaryTree::insert(string data)
{
	insert(data,root);
}

//Alternate insert with just a BinaryNode
void BinaryTree::insert(BinaryNode* added)
{
	insert(added,root);
}

//takes the data string and compares it to the current string, and either recursively adds it to 
//the correct child node or creates a new node to make it.
void BinaryTree::insert(string data, BinaryNode* current)
{
	int dataNum = stringToInt(data);	//make integers to use to compare
	int currentNodeDataNum = stringToInt(current->data);

	//compare data
	if (dataNum > currentNodeDataNum)
	{
		BinaryNode* childNode = current->getRight();
		if (childNode)	//if the childnode is not null, it means we need to insert the data using the child node
		{
			insert(data, childNode);
		}
		else	//but if it is, we make a new node and store the data there
		{
			childNode = new BinaryNode(data);
			current->setRight(childNode);
		}
	}
	else if (dataNum < currentNodeDataNum)
	{
		BinaryNode* childNode = current->getLeft();
		if (childNode)	//if the childnode is not null, it means we need to insert the data using the child node
		{
			insert(data, childNode);
		}
		else	//but if it is, we make a new node and store the data there
		{
			//BinaryNode tempNode  = new BinaryNode(data);
			childNode = new BinaryNode(data);
			current->setLeft(childNode);
		}
	}
	//Note that if the node is equal to a node already in the tree, nothing happens.  This prevents duplicate values.
	
}

//Takes a BinaryNode, and either recursively adds it to 
//the correct child node or creates a new node to make it.
void BinaryTree::insert(BinaryNode* added, BinaryNode* current)
{
	int dataNum = stringToInt(added->data);	//make integers to use to compare
	int currentNodeDataNum = stringToInt(current->data);

	//compare data
	if (dataNum > currentNodeDataNum)
	{
		BinaryNode* childNode = current->getRight();
		if (childNode)	//if the childnode is not null, it means we need to insert the data using the child node
		{
			insert(added, childNode);
		}
		else	//but if it is, we make a new node and store the data there
		{
			current->setRight(added);
		}
	}
	else if (dataNum < currentNodeDataNum)
	{
		BinaryNode* childNode = current->getLeft();
		if (childNode)	//if the childnode is not null, it means we need to insert the data using the child node
		{
			insert(added, childNode);
		}
		else	//but if it is, we make a new node and store the data there
		{
			current->setLeft(added);
		}
	}
	else
	{
		delete added;
	}
	//Note that if the node is equal to a node already in the tree, it is not added but the memory is collected.  This prevents duplicate values & memory leaks.
	
}

//Takes in a string and converts it to an int
int BinaryTree::stringToInt(string s)
{
	return atoi(s.c_str());
}

//Removes a node from the tree, starting at the root node
void BinaryTree::removeNode(string target)
{
	removeNode(target,root,&root);
}

//Recursively removes a node from the tree based on target string
void BinaryTree::removeNode(string target, BinaryNode* current, BinaryNode** currentPtr)
{
	//Compare the data, if it's not equal, try the left and right nodes
	if(target!=current->data)
	{
		if(current->getLeft())
		{
			BinaryNode* tmpLeft = current->getLeft();
			removeNode(target,tmpLeft,&(current->left));
		}
		if(current->getRight())
		{
			BinaryNode* tmpRight = current->getRight();
			removeNode(target,tmpRight,(&current->right));
		}
	}
	else //the data is equal, so we store the leaves of this node, remove the current node, and then add the leaves back into the tree
	{
		BinaryNode* tempLeft = NULL; //Store the left temporarily
		BinaryNode* tempRight= NULL; //Store the right temporarily
		if(current->getLeft())
		{ 
			tempLeft = current->getLeft();
		}
		if(current->getRight())
		{
			tempRight = current->getRight();
		}
		current->isolateNode(); //Isolate the current node so that we dont delete all the rest
		BinaryNode* tempCurr = current; //Stores the current node so the memory can be freed without getting rid of the original pointer
		*currentPtr = NULL; //Sets the ACTUAL current node (not the parameter one) to NULL
		delete tempCurr; //Get rid of the node that existed at current before

		if(tempLeft)
			insert(tempLeft); //reinsert left if there was a left node
		if(tempRight)
			insert(tempRight); //reinsert right if there was a right node
	}
}

//Returns the lowest node in the tree
BinaryNode* BinaryTree::getLowest(BinaryNode* current)
{
	if(current->getRight())
	{
		getLowest(current->getRight());
	}
	else if(current->getLeft())
	{
		getLowest(current->getLeft());
	}
	else
	{
		return current;
	}
}

//Alternate getLowest without any parameters
BinaryNode* BinaryTree::getLowest()
{
	return getLowest(root);
}

//Deletes the tree by deleting the nodes, starting at the root
BinaryTree::~BinaryTree()
{
	delete root;
}